package com.fufu.algorithem.recursion;

import java.util.Arrays;

/**
 * 迷宫问题
 * @author: BlcakTiger
 * @date: 2023/2/19 16:42
 * @contact: hsf6661@163.com
 */
public class Maze {

    public static void main(String[] args) {
        int[][] map = new int[7][8];
        for (int i = 0; i < map.length; i++) {
            map[i][0] = 1;
            map[i][7] = 1;
            map[0][i] = 1;
            map[6][i] = 1;
        }
        changeMap(map);
        boolean res = setWay(map,1,1);
        for (int i = 0; i < map.length; i++) {
            for (int j = 0; j < map[i].length; j++) {
                System.out.print(map[i][j]+" ");
            }
            System.out.println();
        }
        System.out.println("能否走到终点:"+res);
    }

    public static void changeMap(int[][] map){
        map[2][1] = 1;
        map[2][2] = 1;
        map[2][3] = 1;
        map[2][4] = 1;
        map[2][6] = 1;
        map[3][6] = 1;
        map[4][6] = 1;
        map[4][2] = 1;
        map[4][3] = 1;
        map[4][4] = 1;
        map[4][5] = 1;
    }

    /**
     * 约定：1表示墙壁 2表示已经走过的位置 3表示死路，哪个方向都不能走了 0表示还未涉足的地方  5到达目的地
     * @param map 地图数组
     * @param m 横坐标位置
     * @param n 纵坐标位置
     * @return 返回当前位置是否可以走到
     */
    public static boolean setWay(int[][] map,int m,int n){
        //如果当前坐标能够到达指定位置，说明已经走到了指定位置，将其标记为5，返回true
        if (m==5&&n==6) {
            map[m][n] = 5;
            return true;
        }
        //如果当前位置还未涉足，走到该位置，然后判断下一步走向
        if (map[m][n]==0){
            //标记位置
            map[m][n] = 2;
            //downward
            if (setWay(map,m,n+1)){
                return true;
                //right
            }else if (setWay(map,m+1,n)){
                return true;
                //left
            }else if (setWay(map,m-1,n)){
                return true;
                //upward
            }else if (setWay(map,m,n-1)){
                return true;
                //死路，已经无法移动了
            }else {
                map[m][n] = 3;
                return false;
            }
            //如果当前位置不是0，那么就只可能是其他不能走的情况，故而直接返回false
        }else {
            return false;
        }
    }
}
